package com.LeeCode;

/**
 * 最短且字典序最小的美丽子字符串
 */

public class Code2904 {
    public static void main(String[] args) {
        String s = "001110101101101111";
        int k = 10;
        System.out.println(new Code2904().shortestBeautifulSubstring(s, k));

    }

    public String shortestBeautifulSubstring(String s, int k) {
        if (s.replace("0", "").length() < k) return "";

        int left = 0, count = 0;
        char[] chars = s.toCharArray();
        String ans = s;

        for (int right = 0; right < chars.length; right++) {
            count += chars[right] - '0';

            while (count > k || chars[left] == '0') {
                count -= chars[left] - '0';
                left++;
            }
            if (count == k) {
                String temp = s.substring(left, right + 1);
                if (temp.length() < ans.length() || temp.length() == ans.length() && temp.compareTo(ans) < 0)
                    ans = temp;
            }
        }
        return ans;
    }
}
